/*
 * multiply.cpp
 *
 *  Created on: May 23, 2011
 *      Author: Manslaughter
 */

#include "BigInt.h"
#include <stdlib.h>
#include <assert.h>
using namespace APIAL;

void APIAL::Multiply(BigInt* left, BigInt* right, BigInt* result) {
	// TODO: handle aliasing
	assert(left  != result);
	assert(right != result);
	
	// Save original left and right signs
	bool originalLeftPositive = left->positive;
	bool originalRightPositive = right->positive;
	left->positive = true;
	right->positive = true;
	result->positive = true;

	// Determine maximum result size, resize if necessary
	//  Set result to 0.
	int result_size = left->size + right->size + 1;
	if (result->capacity < result_size)
		result->resize(result_size, false);
	memset(result->chunks, 0, result->capacity*sizeof(BigInt::chunkType));

	// Determine which operand has minimum # of 1s --> set as multiplier
	// TODO: Actually implement this functionality
	//       (for now we just set left operand as multiplier)
	BigInt* multiplier = left;
	
	// Multiplicand must be a temporary variable w/ copied values and resized
	// Also create scratch data for add
	BigInt* multiplicand = new BigInt(*right);
	multiplicand->resize(result_size, true);
	BigInt* scratchData = new BigInt(result_size);
	
	// Second BigInt result buffer (to prevent aliasing)
	BigInt* result2 = new BigInt(result_size);
	bool storeToBuf2 = true;	// Store into second result buffer
	int shift_amt = 0;			// Amount to shift multiplicand(s)
	bool ignoreLSB = false;		// Optimization flag for carry bit of 1

	// Loop: Use shift-and-add multiplication for each chunk 
	for (int c = 0; c < multiplier->size; c++) {
		for (int b = 0; b < multiplier->nonCarryBits; b++) {
			// If at LSB and ignoreLSB flag is set --> reset it and skip loop iteration
			if (b == 0 && ignoreLSB) {
				ignoreLSB = false;
				continue;
			}

			// Mask multiplier bit; if bit = 1 add shifted multiplicand to result
			if ( (multiplier->chunks[c] & (1 << b)) != 0 ) {
				LeftShift(multiplicand, shift_amt, multiplicand);
				BigInt::addNoCheck(multiplicand, storeToBuf2?result:result2, scratchData, storeToBuf2?result2:result, 0, multiplicand->size);
				shift_amt = 0;
				storeToBuf2 = !storeToBuf2;		// Toggle which buffers to store to
			}

			// Increment shift amount each time	
			shift_amt++;					
		}
		
		if ( (multiplier->chunks[c] & multiplier->carryBitsMask) != 0 ) {
			// NOTE: Although this uses carryBitsMask, rest of code assumes only 1 carry bit
			if ( (c+1 < multiplier->size) && ((multiplier->chunks[c+1] & 1) != 0) ) {
				// Double shift
				shift_amt++;
			}
			ignoreLSB = true;
			LeftShift(multiplicand, shift_amt, multiplicand);
			BigInt::addNoCheck(multiplicand, storeToBuf2?result:result2, scratchData, storeToBuf2?result2:result, 0, multiplicand->size);
			shift_amt = 1;					// Increment shift amount each time
			storeToBuf2 = !storeToBuf2;		// Toggle which buffers to store to
		}
	}

	// Ensure final product value is in the result buffer
	if (!storeToBuf2) {
		BigInt::chunkType* tmp = result->chunks;
		result->chunks = result2->chunks;
		result->size = result2->size;
		result2->chunks = tmp;
	}

	// Restore signs
	left->positive = originalLeftPositive;
	right->positive = originalRightPositive;
	result->positive = originalLeftPositive == originalRightPositive;

	// Free dynamic variables
	delete result2;
	/*
		TODO: running unit tests in debug reveals a free error on the next line.
		Note that the error is the multiplicand, which is frequently being shifted
		left, with aliasing.  This is likely the source of the bug.
	*/
	delete multiplicand;
	delete scratchData;
}
